package com.wc.alorithm_blue_bridge._动态规划.背包问题._01背包.Q563_采药;

import java.util.Scanner;

/**
 * @Author congge
 * @Date 2024/1/21 11:49
 * @description https://www.lanqiao.cn/problems/563/learning/?page=1&first_category_id=1&tag_category_id=38
 */
public class Main {
    static int N = 1010;
    static int[] f = new int[N];
    static int m, n;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();

        for (int i = 1; i <= n; i++) {
            int w = sc.nextInt();
            int v = sc.nextInt();
            for (int j = m; j >= w; j--) {
                f[j] = Math.max(f[j], f[j - w] + v);
            }
        }
        System.out.println(f[m]);
    }
}
